package bishi2016;

import java.util.HashMap;

public class Tencent_MorethanHalfNum {

	public static void main(String[] args) {
		int[] gifts = {5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,
				5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,
				5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297,5297};
		Tencent_MorethanHalfNum kk = new Tencent_MorethanHalfNum();
		System.out.println(kk.getValue(gifts, 0));
	}
	public int getValue(int[] gifts, int n) {
        if(gifts == null || gifts.length <= 0 || !morethanHalf(gifts)){
            return 0;
        }
        int result = 0, times = 0;
        for(int i = 0; i < gifts.length; i++){
        	if(times == 0){
        		times = 1;
        		result = gifts[i];
        	}else {
        		if(gifts[i] != result){
                    times--;
                }else{
                    times++;
                }
			}
        }
        return result;
    }
    
    public boolean morethanHalf(int[] gifts){
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        Integer value = null;
        for(int i = 0; i < gifts.length; i++){
            value = hash.get(gifts[i]);
            hash.put(gifts[i], value == null ? 1 : value + 1);
            if(hash.get(gifts[i]) > gifts.length / 2){
            	System.out.println("return true");
                return true;
            }
        }
        System.out.println("return false");
        return false;
    }
}
